package com.justnow.dp;

import java.lang.reflect.Field;
import java.util.Arrays;

/**
 * @author justnow
 * Created on 2020-09-22
 * Description
 * <p>
 * 1. 状态
 * 定义dp[i]为考虑前i个元素，以第i个数字结尾的最长上升子序列的长度，注意nums[i]必须被选取
 * <p>
 * 2. 转移方程
 * 从小到大计算dp[]的数组的值，在计算dp[i]之前，先计算出dp[0....i-1]的值，则，状态转移方程为：
 * dp[i] = max(dp[j]) + 1，其中0<= j < i且num[j] < num[i]
 * <p>
 * 3. 最大值
 * 最大值为dp数组中的最大值。
 */
public class Leetcode300 {
    public int lengthOfLIS(int[] nums) {
        int length = nums.length;
        if (length < 2) {
            return length;
        }
        //第一步：定义状态
        //dp[i]表示以nums[i]结尾的上升子序列的最大长度，nums[i]必须被选取，且必须是这个序列的最后一个元素。
        int[] dp = new int[length];
        Arrays.fill(dp, 1);
        int res = 1;
        //第二步：状态转移方程
        //j的大小为[0, i),即j的取值范围为0<=j<=i-1，
        //如果nums[i] > nums[j]，那么此时dp[i] = dp[j] + 1。
        //如果nums[i] <= nums[j]，那么此时nums[i]无法接在nums[j]之后，此情况上升子序列不成立，跳过。
        //但是在判断的过程中，j的值是从小到大递增的，需要挑选出最大的dp[j]
        //那么最后dp[i] = max(dp[j]) + 1, 0<j<i-1, 且nums[i] > nums[j]
        //或者我们换一个角度来看问题
        //dp[i]的值随着j的遍历, 其实是变化的，所以，我们只需要的结果是原来dp[i]和dp[j] + 1之间的最大值
        //dp[i] = max(dp[i], dp[j] + 1);
        //下面举个例子：数组为[1, 2, 8, 4];
        //当我们要计算dp[3]的时候，就需要从判断从0到2之前的情况，
        //首先dp[0] = 1
        //然后dp[1] = 2
        //然后dp[2] = 3
        //然后dp[3] = dp[1] + 1，因为下标为2的元素为8，大于4，所以直接跳过
        for (int i = 1; i < length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }


    /**
     * 方法二，
     * @param nums
     * @return
     */
    public int lengthOfLIS2(int[] nums) {
        if (nums.length <= 0) {
            return 0;
        }

        int length = nums.length;
        int[] dp = new int[length];
        int res = 1;
        dp[0] = 1;
        //那么最后dp[i] = max(dp[j]) + 1, 0<j<i-1, 且nums[i] > nums[j]
        for (int i = 1; i < length; i++) {
            int maxdpj = 0;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    maxdpj = Math.max(maxdpj, dp[j]);
                }
            }
            dp[i] = maxdpj + 1;
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}


